Techniques for estimating the internal state of an observation target, changing from moment to moment, may use time-series filtering. Assuming that a state vector xt indicates the internal state of an object at time t and an observation vector yt indicates a feature observed at time t, time-series filtering is a technique for estimating an internal state xt of a directly unobservable object by using the observation vector yt obtained through observation.
More specifically, time-series filtering is a technique for determining a conditional probability distribution p(xt|y1:t) of a state series x0:t={x0, x1, . . . xt} using the state space models below, when an observation series (a set of observation vectors before time t) y1:t={y1, y2, . . . yt} is given.
System model: xt˜f(xt|xt-1)
Observation model: yt˜h(yt|xt)
With a system noise vt and an observation noise wt, the system model showing the internal state of an object and the observation model formed by observing the object can be expressed as follows:
the system model showing the internal state of an object: xt=f(xt-1, vt)
the observation model formed by observing the object: yt=h(xt, wt)
where f(xt-1, vt) is a state transition function indicating a change in the state between time t−1 and time t, and h(xt, wt) is an observation vector obtained in the state xt. In this case, the one-step ahead prediction is written as the formula below.Formula 1p(xt|y1:t-1)=∫p(xt-1|y1:t-1)f(xt|xt-1)dxt-1  (1)Based on Bayes' theorem, the posterior probability distribution p(xt|y1:t) at time t is written as the formula below.
                    Formula        ⁢                                  ⁢        2                                                                      p          ⁡                      (                                          x                t                            |                              y                                  1                  :                  t                                                      )                          =                                            h              ⁡                              (                                                      y                    t                                    |                                      x                    t                                                  )                                      ⁢                          p              ⁡                              (                                                      x                    t                                    |                                      y                                          1                      :                                              t                        -                        1                                                                                            )                                                          p            ⁡                          (                                                y                  t                                |                                  y                                      1                    :                                          t                      -                      1                                                                                  )                                                          (        2        )            
In this formula, h(yt|xt) is a likelihood (a probability for obtaining an observation vector yt in the state xt), and p(xt|y1:t-1) is a predictive probability distribution.
One practical example of time-series filtering is particle filtering. Particle filters represent the distribution of probabilities of the internal state of an observation target as the distribution of particles, and use the distribution of posterior probabilities of the state at the current time step as the distribution of prior probabilities of the state at the next time step. With particle filtering, the likelihood is calculated by comparing a template observation estimated from the state of particles indicating the distribution of prior probabilities (a set of samples generated in accordance with the prior probability distribution) (predictive samples) with an actual image (an actual observation) obtained at the next time step.
Particle filtering estimates the posterior probability distribution of particles from the calculated likelihoods and the predictive probability distribution.
Particle filtering uses the above processing performed repeatedly at each subsequent time step to successively estimate the dynamically changing state of an observation target (e.g., a tracking target).
Particle filtering involves the processing (1) to (4) below, in which M is the number of particles (M is a natural number) and 1≦i≦M (i is an integer).
(1) Generating Particles (One-Step Ahead Prediction)
For each sample (each particle), the processing corresponding to the formula below is performed to generate a predictive sample at time t. More specifically, the probability distribution (predictive probability distribution) predicted in accordance with the system model (state transition function) is obtained from the posterior probability distribution at time t−1 (the probability distribution of the internal state of an observation target at time t−1). In more detail, each predictive sample is generated from the corresponding sample (particle) at time t−1 through transition in accordance with the system model f.xat(i)˜f(xt|xt-1(i))xat={xat(1),xat(2),xat(3), . . . xat(M)}where xat is a predictive (estimated) vector of a state vector xt calculated by a state transition function f( ).(2) Calculating Weights (Calculating Likelihoods)
For each predictive sample generated in processing (1), the processing corresponding to the formula below is performed to calculate a weight (likelihood). More specifically, the probability (likelihood) to obtain the observation vector yt is estimated in accordance with the observation model h.wat(i)˜h(yt|xat(i))wat={wat(1),wat(2),wat(3), . . . wat(M)}where wat is a predictive (estimated) vector of a weight (likelihood) wt (a set of predictive likelihoods) calculated by a function h( ).(3) Resampling
At the ratio proportional to the weight (likelihood) wat(i), M particles are sampled without changing the total number of the particles (the particle xat(i) is sampled). The posterior probability distribution at time t (the probability distribution of the internal state of the observation target at time t) is obtained from the sampled M particles.
(4) The Time t is Incremented, and the Processing Returns to (1).
The posterior probability distribution obtained in processing (3) (the posterior probability distribution at time t) is used as the prior probability distribution at the next time step (time t+1).
As described above, particle filtering allows the estimation of parameters indicating the changing state of the observation target, changing from moment to moment, by repeatedly predicting the prior probability distribution of parameters indicating the state of the observation target and calculating the posterior probability distribution. Such particle filtering may be used in tracking the position of an object in a moving image. In tracking the position of an object with particle filtering, parameters indicating the state of a tracking target (an example of an observation target) may be, for example, parameters indicating the position of an object. Particle filtering includes comparing observations estimated from parameters indicating the position of the object (predictive samples) with actual observations (e.g., an image captured by a camera) to calculate likelihoods, and resampling particles based on the calculated likelihoods to obtain the posterior probability distribution of parameters indicating the state of the observation target (see, for example, Patent Literature 1: Japanese Unexamined Patent Publication No 2012-234466).